package com.example.wangzh.mytest.part.buchheim_algorithm;

import java.util.LinkedList;

public class TreeLayout {

    public static class Node {
        private String name;
        private Node parent;
        private final LinkedList<Node> children = new LinkedList<>();
        private Node leftSibling;
        private Node rightSibling;
        private double xCoord;
        private double yCoord;
        private double prelim;
        private double modifier;
        private double leftSize = 10;
        private double rightSize = 10;
        private Node ancestor;
        private Node thread;
        private double shift;
        private double change;
        private int indexInParent = 0;

        public Node(String name) {
            this.name = name;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        public Node getParent() {
            return parent;
        }

        public void setParent(Node parent) {
            this.parent = parent;
        }

        public Node getFirstChild() {
            Node firstChild = null;
            try {
                firstChild = children.getFirst();
            } catch (Exception ignored) {
            }
            return firstChild;
        }

        public Node getLastChild() {
            Node lastChild = null;
            try {
                lastChild = children.getLast();
            } catch (Exception ignored) {
            }
            return lastChild;
        }

        public Node getLeftSibling() {
            return leftSibling;
        }

        public void setLeftSibling(Node leftSibling) {
            this.leftSibling = leftSibling;
        }

        public Node getRightSibling() {
            return rightSibling;
        }

        public void setRightSibling(Node rightSibling) {
            this.rightSibling = rightSibling;
        }

        public double getXCoord() {
            return xCoord;
        }

        public void setXCoord(double xCoord) {
            this.xCoord = xCoord;
        }

        public double getYCoord() {
            return yCoord;
        }

        public void setYCoord(double yCoord) {
            this.yCoord = yCoord;
        }

        public double getPrelim() {
            return prelim;
        }

        public void setPrelim(double prelim) {
            this.prelim = prelim;
        }

        public double getModifier() {
            return modifier;
        }

        public void setModifier(double modifier) {
            this.modifier = modifier;
        }

        public double getLeftSize() {
            return leftSize;
        }

        public void setLeftSize(double leftSize) {
            this.leftSize = leftSize;
        }

        public double getRightSize() {
            return rightSize;
        }

        public void setRightSize(double rightSize) {
            this.rightSize = rightSize;
        }

        public Node getAncestor() {
            return ancestor;
        }

        public void setAncestor(Node ancestor) {
            this.ancestor = ancestor;
        }

        public Node getThread() {
            return thread;
        }

        public void setThread(Node thread) {
            this.thread = thread;
        }

        public double getShift() {
            return shift;
        }

        public void setShift(double shift) {
            this.shift = shift;
        }

        public double getChange() {
            return change;
        }

        public void setChange(double change) {
            this.change = change;
        }

        public int getIndexInParent() {
            return indexInParent;
        }

        public void setIndexInParent(int indexInParent) {
            this.indexInParent = indexInParent;
        }

        public boolean isLeaf() {
            return children.size() == 0;
        }

        public boolean hasLeftSibling() {
            return leftSibling != null;
        }

        public boolean hasRightSibling() {
            return rightSibling != null;
        }

        public boolean hasChild() {
            return children.size() > 0;
        }

        @SuppressWarnings("UnusedReturnValue")
        public boolean addChild(Node child) {
            boolean result = children.add(child);
            if (!result) {
                return false;
            }
            handleRelations(child);
            return true;
        }


        public boolean addChild(Node leftSibling, Node child) {
            int leftIndex = children.indexOf(leftSibling);
            if (leftIndex == -1) {
                return false;
            }
            children.add(leftIndex + 1, child);
            handleRelations(child);
            return true;
        }

        private void handleRelations(Node child) {
            child.setParent(this);
            int index = children.indexOf(child);
            if (index == -1) {
                throw new IllegalStateException("child added,but no index");
            }
            if (index > 0) {
                Node leftSibling = children.get(index - 1);
                leftSibling.setRightSibling(child);
                child.setLeftSibling(leftSibling);
            }

            if (index < children.size() - 1) {
                Node rightSibling = children.get(index + 1);
                rightSibling.setLeftSibling(child);
                child.setRightSibling(rightSibling);
            }
        }

    }

    private static final double LEVEL_SEPARATION = 100;
    private static final double SIBLING_SEPARATION = 40;
    private static final double SUBTREE_SEPARATION = 40;

    private static double xTopAdjustment;
    private static double yTopAdjustment;

    public void layoutTree(Node root) {
        initializeNodes(root);
        firstWalk(root);
        xTopAdjustment = root.getXCoord() - root.getPrelim();
        yTopAdjustment = root.getYCoord();
        secondWalk(root, 0, 0);
    }

    private void initializeNodes(Node node) {
        if (node == null) return;
        node.modifier = 0;
        node.thread = null;
        node.ancestor = node;
        node.shift = 0;
        node.change = 0;
        Node child = node.getFirstChild();
        while (child != null) {
            initializeNodes(child);
            int tempIndex = child.indexInParent;
            child = child.rightSibling;
            if (child != null) {
                child.indexInParent = tempIndex + 1;
            }
        }
    }

    private void firstWalk(Node v) {
        if (v.isLeaf()) {
            v.prelim = 0;
            if (v.hasLeftSibling()) {
                double distance = getSiblingDistance(v.leftSibling, v);
                v.prelim = v.leftSibling.prelim + distance;
            }
        } else {
            Node defaultAncestor = v.getFirstChild();
            Node w = v.getFirstChild();
            while (w != null) {
                firstWalk(w);
                apportion(w, defaultAncestor);
                w = w.rightSibling;
            }
            executeShifts(v);
            Node leftmost = v.getFirstChild();
            Node rightmost = v.getLastChild();
            double midpoint = 0.5 * (leftmost.prelim + rightmost.prelim);
            Node leftSibling = v.leftSibling;
            if (leftSibling != null) {
                double distance = getSiblingDistance(leftSibling, v);
                v.prelim = leftSibling.prelim + distance;
                v.modifier = v.prelim - midpoint;
            } else {
                v.prelim = midpoint;
            }
        }
    }

    private double getSiblingDistance(Node left, Node right) {
        return left.rightSize + right.leftSize + SIBLING_SEPARATION;
    }

    private double getNeighborDistance(Node left, Node right) {
        return left.rightSize + right.leftSize + SUBTREE_SEPARATION;
    }

    private void apportion(Node v, Node defaultAncestor) {
        Node w = v.leftSibling;
        if (w == null) return;
        Node vip = v;
        Node vop = v;
        Node vim = w;
        Node vom = vip.parent.getFirstChild();
        double sip = vip.modifier;
        double sop = vop.modifier;
        double sim = vim.modifier;
        double som = vom.modifier;

        while (nextRight(vim) != null && nextLeft(vip) != null) {
            vim = nextRight(vim);
            vip = nextLeft(vip);
            vom = nextLeft(vom);
            vop = nextRight(vop);
            vop.ancestor = v;
            double shift = (vim.prelim + sim) - (vip.prelim + sip) + getNeighborDistance(vim, vip);
            if (shift > 0) {
                Node ancestor = ancestor(vim, v, defaultAncestor);
                moveSubtree(ancestor, v, shift);
                sip += shift;
                sop += shift;
            }

            sim += vim.modifier;
            sip += vip.modifier;
            som += vom.modifier;
            sop += vop.modifier;
        }

        if (nextRight(vim) != null && nextRight(vop) == null) {
            vop.thread = nextRight(vim);
            vop.modifier += sim - sop;
        }

        if (nextLeft(vip) != null && nextLeft(vom) == null) {
            vom.thread = nextLeft(vip);
            vom.modifier += sip - som;
            defaultAncestor = v;
        }
    }

    private Node nextLeft(Node v) {
        if (v.getFirstChild() != null) {
            return v.getFirstChild();
        } else {
            return v.thread;
        }
    }

    private Node nextRight(Node v) {
        if (v.getFirstChild() != null) {
            return v.getLastChild();
        } else {
            return v.thread;
        }
    }

    private void moveSubtree(Node wm, Node wp, double shift) {
        int subtrees = wp.indexInParent - wm.indexInParent;
        wp.change -= shift / subtrees;
        wp.shift += shift;
        wm.change += shift / subtrees;
        wp.prelim += shift;
        wp.modifier += shift;
    }

    private void executeShifts(Node v) {
        double shift = 0;
        double change = 0;
        Node w = v.getLastChild();
        while (w != null) {
            w.prelim += shift;
            w.modifier += shift;
            change += w.change;
            shift += w.shift + change;
            w = w.leftSibling;
        }
    }

    private Node ancestor(Node vim, Node v, Node defaultAncestor) {
        if (vim.ancestor != null && vim.ancestor.parent == v.parent) {
            return vim.ancestor;
        } else {
            return defaultAncestor;
        }
    }

    private void secondWalk(Node v, double m, int level) {
        v.xCoord = xTopAdjustment + v.prelim + m;
        v.yCoord = yTopAdjustment + level * LEVEL_SEPARATION; // 根据层级设置y坐标
        Node child = v.getFirstChild();
        while (child != null) {
            secondWalk(child, m + v.modifier, level + 1);
            child = child.rightSibling;
        }
    }
}